/*
    8. Write a C program to sort a list of elements using the radix sort algorithm. 
    Radix sort is a non-comparative integer sorting algorithm that sorts data with 
    integer keys by grouping keys by the individual digits which share the same
    significant position and value.
*/

#include <stdio.h>
#include <string.h>

int getDigitNum(int num, int digit){
    int i = 0;
    while(i < digit){
        num = num / 10;
        i++;
    }
    return num % 10;
}

int getMaxDigitCnt(int a[], int len){
    int cnt, i, tmp;
    int maxCnt = 0;
    for(i = 0; i < len; i++){
        tmp = a[i];
        cnt = 0;
        while(tmp){            
            cnt++;
            tmp /= 10;
        }
        if(cnt > maxCnt){
            maxCnt = cnt;
        }
    }
    return maxCnt;
}

void radixSort(int a[], int len){
    int bucket[10][64];
    int i, j, k, idx;
    int digitNum, digitIdx[10];
    int maxloop = getMaxDigitCnt(a, len);    
    for(i = 0; i < maxloop; i++){
        memset(digitIdx, 0, sizeof(digitIdx));
        for(j = 0; j < len; j++){ //put array into bucket
            digitNum = getDigitNum(a[j], i);
            bucket[digitNum][digitIdx[digitNum]++] = a[j];
            
        }
        idx = 0;
        for(j = 0; j < 10; j++){ //resume to array from bucket
            for(k = 0; k < digitIdx[j]; k++){
                a[idx++] = bucket[j][k];
                printf("%d, ", bucket[j][k]);
            }
        }
        printf("|idx = %d|\n", idx);
    }
}

void printarray(int a[], int len)
{
    int i;
    for(i = 0; i < len; i++){
        printf("%d, ", a[i]);
    }
    printf("\n");
}

int main(void)
{
    int a[] = {25, 31, 2, 6, 3, 8, 55, 26, 1234, 45, 95, 1};
    int len = sizeof(a) / sizeof(int);
    printf("%d, %d, %d\n", getDigitNum(123, 2), getDigitNum(123, 1), getDigitNum(123, 0));
    printf("maxcnt = %d\n", getMaxDigitCnt(a, len));
    radixSort(a, len);
    printarray(a, len);
    return 0;
}